//===--- PILConstants.h - PIL constant representation -----------*- C++ -*-===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
//
// This defines an interface to represent PIL level structured constants in a
// memory efficient way.
//
//===----------------------------------------------------------------------===//

#ifndef POLARPHP_PIL_CONSTANTS_H
#define POLARPHP_PIL_CONSTANTS_H

#include "polarphp/ast/SubstitutionMap.h"
#include "polarphp/pil/lang/PILValue.h"
#include "llvm/Support/CommandLine.h"

namespace polar {

class SingleValueInstruction;
class PILValue;
class PILBuilder;
class SerializedPILLoader;

struct AggregateSymbolicValue;
struct SymbolicArrayStorage;
struct DerivedAddressValue;
struct EnumWithPayloadSymbolicValue;
struct SymbolicValueMemoryObject;
struct UnknownSymbolicValue;
struct SymbolicClosure;

extern llvm::cl::opt<unsigned> ConstExprLimit;

/// An abstract class that exposes functions for allocating symbolic values.
/// The implementors of this class have to determine where to allocate them and
/// and manage the lifetime of the allocated symbolic values.
class SymbolicValueAllocator {
public:
   virtual ~SymbolicValueAllocator() {}

   /// Allocate raw bytes.
   /// \param byteSize number of bytes to allocate.
   /// \param alignment alignment for the allocated bytes.
   virtual void *allocate(unsigned long byteSize, unsigned alignment) = 0;

   /// Allocate storage for a given number of elements of a specific type
   /// provided as a template parameter. Precondition: \c T must have an
   /// accesible zero argument constructor.
   /// \param numElts number of elements of the type to allocate.
   template <typename T> T *allocate(unsigned numElts) {
      T *res = (T *)allocate(sizeof(T) * numElts, alignof(T));
      for (unsigned i = 0; i != numElts; ++i)
         new (res + i) T();
      return res;
   }
};

/// A class that allocates symbolic values in a local bump allocator. The
/// lifetime of the bump allocator is same as the lifetime of \c this object.
class SymbolicValueBumpAllocator : public SymbolicValueAllocator {
private:
   llvm::BumpPtrAllocator bumpAllocator;

public:
   SymbolicValueBumpAllocator() {}
   ~SymbolicValueBumpAllocator() {}

   void *allocate(unsigned long byteSize, unsigned alignment) {
      return bumpAllocator.Allocate(byteSize, alignment);
   }
};

/// When we fail to constant fold a value, this captures a reason why,
/// allowing the caller to produce a specific diagnostic.  The "Unknown"
/// SymbolicValue representation also includes a pointer to the PILNode in
/// question that was problematic.
class UnknownReason {
public:
   enum UnknownKind {
      // TODO: Eliminate the default kind, by making classifications for each
      // failure mode.
         Default,

      /// The constant expression was too big.  This is reported on a random
      /// instruction within the constexpr that triggered the issue.
         TooManyInstructions,

      /// A control flow loop was found.
         Loop,

      /// Integer overflow detected.
         Overflow,

      /// Trap detected. Traps will a message as a payload.
         Trap,

      /// An operation was applied over operands whose symbolic values were
      /// constants but were not valid for the operation.
         InvalidOperandValue,

      /// Encountered an instruction not supported by the interpreter.
         UnsupportedInstruction,

      /// Encountered a function call whose arguments are not constants.
         CallArgumentUnknown,

      /// Encountered a function call where the body of the called function is
      /// not available.
         CalleeImplementationUnknown,

      /// Attempted to load from/store into a PIL value that was not tracked by
      /// the interpreter.
         UntrackedPILValue,

      /// Attempted to find a concrete protocol conformance for a witness method
      /// and failed.
         UnknownWitnessMethodConformance,

      /// Attempted to determine the PIL function of a witness method  and failed.
         NoWitnesTableEntry,

      /// The value of a top-level variable cannot be determined to be a constant.
      /// This is only relevant in the backward evaluation mode, which is used by
      /// #assert.
         NotTopLevelConstant,

      /// A top-level value has multiple writers. This is only relevant in the
      /// non-flow-sensitive evaluation mode,  which is used by #assert.
         MutipleTopLevelWriters,

      /// Indicates the return value of an instruction that was not evaluated
      /// during interpretation.
         ReturnedByUnevaluatedInstruction,

      /// Indicates that the value was possibly modified by an instruction
      /// that was not evaluated during the interpretation.
         MutatedByUnevaluatedInstruction,
   };

private:
   UnknownKind kind;

   // Auxiliary information for different unknown kinds.
   union {
      PILFunction *function;   // For CalleeImplementationUnknown
      const char *trapMessage; // For Trap.
      unsigned argumentIndex;  // For CallArgumentUnknown
   } payload;

public:
   UnknownKind getKind() { return kind; }

   static bool isUnknownKindWithPayload(UnknownKind kind) {
      switch (kind) {
         case UnknownKind::CalleeImplementationUnknown:
         case UnknownKind::Trap:
         case UnknownKind::CallArgumentUnknown:
            return true;
         default:
            return false;
      }
   }

   static UnknownReason create(UnknownKind kind) {
      assert(!isUnknownKindWithPayload(kind));
      UnknownReason reason;
      reason.kind = kind;
      return reason;
   }

   static UnknownReason createCalleeImplementationUnknown(PILFunction *callee) {
      assert(callee);
      UnknownReason reason;
      reason.kind = UnknownKind::CalleeImplementationUnknown;
      reason.payload.function = callee;
      return reason;
   }

   PILFunction *getCalleeWithoutImplmentation() {
      assert(kind == UnknownKind::CalleeImplementationUnknown);
      return payload.function;
   }

   static UnknownReason createTrap(StringRef message,
                                   SymbolicValueAllocator &allocator) {
      // Copy and null terminate the string.
      size_t size = message.size();
      char *messagePtr = allocator.allocate<char>(size + 1);
      std::uninitialized_copy(message.begin(), message.end(), messagePtr);
      messagePtr[size] = '\0';

      UnknownReason reason;
      reason.kind = UnknownKind::Trap;
      reason.payload.trapMessage = messagePtr;
      return reason;
   }

   const char *getTrapMessage() {
      assert(kind == UnknownKind::Trap);
      return payload.trapMessage;
   }

   static UnknownReason createCallArgumentUnknown(unsigned argIndex) {
      UnknownReason reason;
      reason.kind = UnknownKind::CallArgumentUnknown;
      reason.payload.argumentIndex = argIndex;
      return reason;
   }

   unsigned getArgumentIndex() {
      assert(kind == UnknownKind::CallArgumentUnknown);
      return payload.argumentIndex;
   }
};

/// This is the symbolic value tracked for each PILValue in a scope.  We
/// support multiple representational forms for the constant node in order to
/// avoid pointless memory bloat + copying.  This is intended to be a
/// light-weight POD type we can put in hash tables and pass around by-value.
///
/// Internally, this value has multiple ways to represent the same sorts of
/// symbolic values (e.g. to save memory).  It provides a simpler public
/// interface though.
class SymbolicValue {
private:
   enum RepresentationKind {
      /// This value is an alloc stack that has not (yet) been initialized
      /// by flow-sensitive analysis.
         RK_UninitMemory,

      /// This symbolic value cannot be determined, carries multiple values
      /// (i.e., varies dynamically at the top level), or is of some type that
      /// we cannot analyze and propagate (e.g. NSObject).
      ///
         RK_Unknown,

      /// This value is known to be a metatype reference.  The type is stored
      /// in the "metatype" member.
         RK_Metatype,

      /// This value is known to be a function reference, e.g. through
      /// function_ref directly, or a devirtualized method reference.
         RK_Function,

      /// This value is represented with a bump-pointer allocated APInt.
         RK_Integer,

      /// This value is represented with an inline integer representation.
         RK_IntegerInline,

      /// This value is represented with a bump-pointer allocated char array
      /// representing a UTF-8 encoded string.
         RK_String,

      /// This value is a struct or tuple of constants.  This is tracked by the
      /// "aggregate" member of the value union.
         RK_Aggregate,

      /// This value is an enum with no payload.
         RK_Enum,

      /// This value is an enum with a payload.
         RK_EnumWithPayload,

      /// This represents the address of a memory object.
         RK_DirectAddress,

      /// This represents an index *into* a memory object.
         RK_DerivedAddress,

      /// This represents the internal storage of an array.
         RK_ArrayStorage,

      /// This represents an array.
         RK_Array,

      /// This represents a closure.
         RK_Closure,
   };

   union {
      /// When the value is Unknown, this contains information about the
      /// unfoldable part of the computation.
      UnknownSymbolicValue *unknown;

      /// This is always a PILType with an object category.  This is the value
      /// of the underlying instance type, not the MetatypeType.
      TypeBase *metatype;

      PILFunction *function;

      /// When this SymbolicValue is of "Integer" kind, this pointer stores
      /// the words of the APInt value it holds.
      uint64_t *integer;

      /// This holds the bits of an integer for an inline representation.
      uint64_t integerInline;

      /// When this SymbolicValue is of "String" kind, this pointer stores
      /// information about the StringRef value it holds.
      const char *string;

      /// When this SymbolicValue is of "Aggregate" kind, this pointer stores
      /// information about the aggregate elements, its type and count.
      const AggregateSymbolicValue *aggregate;

      /// When this SymbolicValue is of "Enum" kind, this pointer stores
      /// information about the enum case type.
      EnumElementDecl *enumVal;

      /// When this SymbolicValue is of "EnumWithPayload" kind, this pointer
      /// stores information about the enum case type and its payload.
      EnumWithPayloadSymbolicValue *enumValWithPayload;

      /// When the representationKind is "DirectAddress", this pointer is the
      /// memory object referenced.
      SymbolicValueMemoryObject *directAddress;

      /// When this SymbolicValue is of "DerivedAddress" kind, this pointer stores
      /// information about the memory object and access path of the access.
      DerivedAddressValue *derivedAddress;

      // The following two fields are for representing an Array.
      //
      // In Swift, an array is a non-trivial struct that stores a reference to an
      // internal storage: _ContiguousArrayStorage. Though arrays have value
      // semantics in Swift, it is not the case in PIL. In PIL, an array can be
      // mutated by taking the address of the internal storage i.e., through a
      // shared, mutable pointer to the internal storage of the array. In fact,
      // this is how an array initialization is lowered in PIL. Therefore, the
      // symbolic representation of an array is an addressable "memory cell"
      // (i.e., a SymbolicValueMemoryObject) containing the array storage. The
      // array storage is modeled by the type: SymbolicArrayStorage. This
      // representation of the array enables obtaining the address of the internal
      // storage and modifying the array through that address. Array operations
      // such as `append` that mutate an array must clone the internal storage of
      // the array, following the semantics of the Swift implementation of those
      // operations.

      /// Representation of array storage (RK_ArrayStorage). SymbolicArrayStorage
      /// is a container for a sequence of symbolic values.
      SymbolicArrayStorage *arrayStorage;

      /// When this symbolic value is of an "Array" kind, this stores a memory
      /// object that contains a SymbolicArrayStorage value.
      SymbolicValueMemoryObject *array;

      /// When this symbolic value is of "Closure" kind, store a pointer to the
      /// symbolic representation of the closure.
      SymbolicClosure *closure;
   } value;

   RepresentationKind representationKind : 8;

   union {
      /// This is the number of bits in an RK_Integer or RK_IntegerInline
      /// representation, which makes the number of entries in the list derivable.
      unsigned integerBitwidth;

      /// This is the number of bytes for an RK_String representation.
      unsigned stringNumBytes;
   } auxInfo;

public:
   /// This enum is used to indicate the sort of value held by a SymbolicValue
   /// independent of its concrete representation.  This is the public
   /// interface to SymbolicValue.
   enum Kind {
      /// This is a value that isn't a constant.
         Unknown,

      /// This is a known metatype value.
         Metatype,

      /// This is a function, represented as a PILFunction.
         Function,

      /// This is an integer constant.
         Integer,

      /// String values may have PIL type of Builtin.RawPointer or Builtin.Word
      /// type.
         String,

      /// This can be an array, struct, tuple, etc.
         Aggregate,

      /// This is an enum without payload.
         Enum,

      /// This is an enum with payload (formally known as "associated value").
         EnumWithPayload,

      /// This value represents the address of, or into, a memory object.
         Address,

      /// This represents an internal array storage.
         ArrayStorage,

      /// This represents an array value.
         Array,

      /// This represents a closure.
         Closure,

      /// These values are generally only seen internally to the system, external
      /// clients shouldn't have to deal with them.
         UninitMemory
   };

   /// For constant values, return the type classification of this value.
   Kind getKind() const;

   /// Return true if this represents a constant value.
   bool isConstant() const {
      auto kind = getKind();
      return kind != Unknown && kind != UninitMemory;
   }

   static SymbolicValue getUnknown(PILNode *node, UnknownReason reason,
                                   llvm::ArrayRef<SourceLoc> callStack,
                                   SymbolicValueAllocator &allocator);

   /// Return true if this represents an unknown result.
   bool isUnknown() const { return getKind() == Unknown; }

   /// Return the call stack for an unknown result.
   ArrayRef<SourceLoc> getUnknownCallStack() const;

   /// Return the node that triggered an unknown result.
   PILNode *getUnknownNode() const;

   /// Return the reason an unknown result was generated.
   UnknownReason getUnknownReason() const;

   static SymbolicValue getUninitMemory() {
      SymbolicValue result;
      result.representationKind = RK_UninitMemory;
      return result;
   }

   static SymbolicValue getMetatype(CanType type) {
      SymbolicValue result;
      result.representationKind = RK_Metatype;
      result.value.metatype = type.getPointer();
      return result;
   }

   CanType getMetatypeValue() const {
      assert(representationKind == RK_Metatype);
      return CanType(value.metatype);
   }

   static SymbolicValue getFunction(PILFunction *fn) {
      assert(fn && "Function cannot be null");
      SymbolicValue result;
      result.representationKind = RK_Function;
      result.value.function = fn;
      return result;
   }

   PILFunction *getFunctionValue() const {
      assert(getKind() == Function);
      return value.function;
   }

   static SymbolicValue getInteger(int64_t value, unsigned bitWidth);
   static SymbolicValue getInteger(const APInt &value,
                                   SymbolicValueAllocator &allocator);

   APInt getIntegerValue() const;
   unsigned getIntegerValueBitWidth() const;

   /// Returns a SymbolicValue representing a UTF-8 encoded string.
   static SymbolicValue getString(StringRef string,
                                  SymbolicValueAllocator &allocator);

   /// Returns the UTF-8 encoded string underlying a SymbolicValue.
   StringRef getStringValue() const;

   /// This returns an aggregate value with the specified elements in it.  This
   /// copies the member values into the specified Allocator.
   static SymbolicValue getAggregate(ArrayRef<SymbolicValue> members,
                                     Type aggregateType,
                                     SymbolicValueAllocator &allocator);

   ArrayRef<SymbolicValue> getAggregateMembers() const;

   /// Return the type of this aggregate symbolic value.
   Type getAggregateType() const;

   /// This returns a constant Symbolic value for the enum case in `decl`, which
   /// must not have an associated value.
   static SymbolicValue getEnum(EnumElementDecl *decl) {
      assert(decl);
      SymbolicValue result;
      result.representationKind = RK_Enum;
      result.value.enumVal = decl;
      return result;
   }

   /// `payload` must be a constant.
   static SymbolicValue getEnumWithPayload(EnumElementDecl *decl,
                                           SymbolicValue payload,
                                           SymbolicValueAllocator &allocator);

   EnumElementDecl *getEnumValue() const;

   SymbolicValue getEnumPayloadValue() const;

   /// Return a symbolic value that represents the address of a memory object.
   static SymbolicValue getAddress(SymbolicValueMemoryObject *memoryObject) {
      SymbolicValue result;
      result.representationKind = RK_DirectAddress;
      result.value.directAddress = memoryObject;
      return result;
   }

   /// Return a symbolic value that represents the address of a memory object
   /// indexed by a path.
   static SymbolicValue getAddress(SymbolicValueMemoryObject *memoryObject,
                                   ArrayRef<unsigned> indices,
                                   SymbolicValueAllocator &allocator);

   /// Return the memory object of this reference along with any access path
   /// indices involved.
   SymbolicValueMemoryObject *
   getAddressValue(SmallVectorImpl<unsigned> &accessPath) const;

   /// Return just the memory object for an address value.
   SymbolicValueMemoryObject *getAddressValueMemoryObject() const;

   /// Create a symbolic array storage containing \c elements.
   static SymbolicValue
   getSymbolicArrayStorage(ArrayRef<SymbolicValue> elements, CanType elementType,
                           SymbolicValueAllocator &allocator);

   /// Create a symbolic array using the given symbolic array storage, which
   /// contains the array elements.
   static SymbolicValue getArray(Type arrayType, SymbolicValue arrayStorage,
                                 SymbolicValueAllocator &allocator);

   /// Return the elements stored in this SymbolicValue of "ArrayStorage" kind.
   ArrayRef<SymbolicValue> getStoredElements(CanType &elementType) const;

   /// Return the symbolic value representing the internal storage of this array.
   SymbolicValue getStorageOfArray() const;

   /// Return the symbolic value representing the address of the element of this
   /// array at the given \c index. The return value is a derived address whose
   /// base is the memory object \c value.array (which contains the array
   /// storage) and whose accesspath is \c index.
   SymbolicValue getAddressOfArrayElement(SymbolicValueAllocator &allocator,
                                          unsigned index) const;

   /// Return the type of this array symbolic value.
   Type getArrayType() const;

   /// Create and return a symbolic value that represents a closure.
   /// \param target PILFunction corresponding the target of the closure.
   /// \param capturedArguments an array consisting of PILValues of captured
   /// arguments along with their symbolic values when available.
   /// \param allocator the allocator to use for storing the contents of this
   /// symbolic value.
   static SymbolicValue makeClosure(
      PILFunction *target,
      ArrayRef<std::pair<PILValue, Optional<SymbolicValue>>> capturedArguments,
      SubstitutionMap substMap, PILType closureType,
      SymbolicValueAllocator &allocator);

   SymbolicClosure *getClosure() const {
      assert(getKind() == Closure);
      return value.closure;
   }

   //===--------------------------------------------------------------------===//
   // Helpers

   /// Dig through single element aggregates, return the ultimate thing inside of
   /// it.  This is useful when dealing with integers and floats, because they
   /// are often wrapped in single-element struct wrappers.
   SymbolicValue lookThroughSingleElementAggregates() const;

   /// Given that this is an 'Unknown' value, emit diagnostic notes providing
   /// context about what the problem is.  If there is no location for some
   /// reason, we fall back to using the specified location.
   void emitUnknownDiagnosticNotes(PILLocation fallbackLoc);

   bool isUnknownDueToUnevaluatedInstructions();

   /// Clone this SymbolicValue into the specified Allocator and return the new
   /// version. This only works for valid constants.
   SymbolicValue cloneInto(SymbolicValueAllocator &allocator) const;

   void print(llvm::raw_ostream &os, unsigned indent = 0) const;
   void dump() const;
};

static_assert(sizeof(SymbolicValue) == 2 * sizeof(uint64_t),
              "SymbolicValue should stay small");
static_assert(std::is_pod<SymbolicValue>::value,
              "SymbolicValue should stay POD");

inline llvm::raw_ostream &operator<<(llvm::raw_ostream &os, SymbolicValue val) {
   val.print(os);
   return os;
}

/// This is a representation of a memory object referred to by an address.
/// Memory objects may be mutated over their lifetime, but their overall type
/// remains the same.
struct SymbolicValueMemoryObject {
   Type getType() const { return type; }

   SymbolicValue getValue() const { return value; }
   void setValue(SymbolicValue newValue) {
      assert((newValue.getKind() != SymbolicValue::Aggregate ||
              newValue.getAggregateType()->isEqual(type)) &&
             "Memory object type does not match the type of the symbolic value");
      value = newValue;
   }

   /// Create a new memory object whose overall type is as specified.
   static SymbolicValueMemoryObject *create(Type type, SymbolicValue value,
                                            SymbolicValueAllocator &allocator);

   /// Given that this memory object contains an aggregate value like
   /// {{1, 2}, 3}, and given an access path like [0,1], return the indexed
   /// element, e.g. "2" in this case.
   ///
   /// Returns uninit memory if the access path points at or into uninit memory.
   ///
   /// Precondition: The access path must be valid for this memory object's type.
   SymbolicValue getIndexedElement(ArrayRef<unsigned> accessPath);

   /// Given that this memory object contains an aggregate value like
   /// {{1, 2}, 3}, given an access path like [0,1], and given a new element like
   /// "4", set the indexed element to the specified scalar, producing {{1, 4},
   /// 3} in this case.
   ///
   /// Precondition: The access path must be valid for this memory object's type.
   void setIndexedElement(ArrayRef<unsigned> accessPath,
                          SymbolicValue newElement,
                          SymbolicValueAllocator &allocator);

private:
   const Type type;
   SymbolicValue value;

   SymbolicValueMemoryObject(Type type, SymbolicValue value)
      : type(type), value(value) {}
   SymbolicValueMemoryObject(const SymbolicValueMemoryObject &) = delete;
   void operator=(const SymbolicValueMemoryObject &) = delete;
};

using SymbolicClosureArgument = std::pair<PILValue, Optional<SymbolicValue>>;

/// Representation of a symbolic closure. A symbolic closure consists of a
/// PILFunction and an array of PIL values, corresponding to the captured
/// arguments, and (optional) symbolic values representing the constant values
/// of the captured arguments. The symbolic values are optional as it is not
/// necessary for every captured argument to be a constant, which enables
/// representing closures whose captured arguments are not compile-time
/// constants.
struct SymbolicClosure final
   : private llvm::TrailingObjects<SymbolicClosure, SymbolicClosureArgument> {

   friend class llvm::TrailingObjects<SymbolicClosure, SymbolicClosureArgument>;

private:

   PILFunction *target;

   // The number of PIL values captured by the closure.
   unsigned numCaptures;

   // True iff there exists a captured argument whose constant value is not
   // known.
   bool hasNonConstantCaptures = true;

   // A substitution map that partially maps the generic paramters of the
   // applied function to the generic arguments of passed to the call.
   SubstitutionMap substitutionMap;

   PILType closureType;

   SymbolicClosure() = delete;
   SymbolicClosure(const SymbolicClosure &) = delete;
   SymbolicClosure(PILFunction *callee, unsigned numArguments,
                   SubstitutionMap substMap, PILType closureType,
                   bool nonConstantCaptures)
      : target(callee), numCaptures(numArguments),
        hasNonConstantCaptures(nonConstantCaptures), substitutionMap(substMap),
        closureType(closureType) {}

public:
   static SymbolicClosure *create(PILFunction *callee,
                                  ArrayRef<SymbolicClosureArgument> args,
                                  SubstitutionMap substMap, PILType closureType,
                                  SymbolicValueAllocator &allocator);

   ArrayRef<SymbolicClosureArgument> getCaptures() const {
      return {getTrailingObjects<SymbolicClosureArgument>(), numCaptures};
   }

   // This is used by the llvm::TrailingObjects base class.
   size_t numTrailingObjects(OverloadToken<SymbolicClosureArgument>) const {
      return numCaptures;
   }

   PILFunction *getTarget() {
      return target;
   }

   PILType getClosureType() { return closureType; }

   SubstitutionMap getCallSubstitutionMap() { return substitutionMap; }
};

} // end namespace polar

#endif
